﻿//day28-01 牛客：游游的重组偶数，题号：10274325
// 解法：数学+swap()函数
//int q;
//string s;
//string fun()
//{
//    int n = s.size();
//    for (int i = n - 1; i >= 0; i--)
//    {
//        if (s[i] % 2 == 0)
//        {
//            swap(s[i], s[n - 1]);
//            return s;
//        }
//    }
//    return "-1";
//}
//int main()
//{
//    cin >> q;
//    while (q--)
//    {
//        cin >> s;
//        cout << fun() << endl;
//    }
//    return 0;
//}


//day28-02 牛客：体操队形，题号：2227705
//解法：DFS+回溯+剪枝
//bool vis[11] = { 0 };
//int n;
//int arr[11];
//int ret;
//
//void dfs(int pos)
//{
//    if (pos == n + 1)
//    {
//        ret++;
//        return;
//    }
//    for (int i = 1; i <= n; i++)
//    {
//        if (!vis[i] && !vis[arr[i]])
//        {
//            vis[i] = true;
//            dfs(pos + 1);
//            vis[i] = false;
//        }
//    }
//}
//int main()
//{
//    cin >> n;
//    for (int i = 1; i <= n; i++) cin >> arr[i];
//    dfs(1);
//    cout << ret << endl;
//    return 0;
//}



//day28-03 牛客：⼆叉树中的最⼤路径和，题号：622
//解法：树形dp
//int ret = -1010;
//int maxPathSum(TreeNode* root)
//{
//	dfs(root);
//	return ret;
//}
//int dfs(TreeNode* root)
//{
//	if (root == nullptr) return 0;
//	int l = max(0, dfs(root->left));// 左⼦树的最⼤单链和
//	int r = max(0, dfs(root->right)); // 右⼦树的最⼤单链和
//	// 经过root的最⼤路径和
//	ret = max(ret, root->val + l + r);
//	return root->val + max(l, r);
//}